Package edu.claflin.finder.logic

Class Graph

java.lang.Object
edu.claflin.finder.logic.Graph
Direct Known Subclasses:
ConditionedGraph
public class Graph extends Object
Used to represent a graph in memory. Migrated from matrix form, the graph is now kept track of via a list of edges and nodes. All the previous methods remain in existence but the underlying implementation has changed.
Version:
3.4 February 2, 2016
Author:
Charles Allen Schultz II

  • Field Details

    • graphName

      private final String graphName
      The name of the Graph provided by the user. This value is used by the program to name output files unless specified otherwise.

    • nodeList

      private final ArrayList<Node> nodeList
      The list of the nodes added to the graph. Used by the program to keep track of the associations within the matrix. It may be re-ordered dynamically at runtime.

    • edgeList

      private final ArrayList<Edge> edgeList
      The list of edges added to the graph. The graph is, by default, a directed graph. As such, two edges must be added to force the graph to be bidirectional.

    • weight

      private double weight

    • suppressLog

      protected boolean suppressLog
      Used to suppress logging.

  • Constructor Details

    • Graph

      public Graph(String graphName)
      Initializes the graph. Merely initializes fields. It does not set any data. Also sets the Logging Utility object. If null, the class will not log data.
      Parameters:
      graphName - the String which represents the name of the Graph.

    • Graph

      public Graph(String graphName, List<Node> nodeList, List<Edge> edgeList)
      Private constructor used by subGraph method.
      Parameters:
      graphName - the String which represents the name of the Graph.
      nodeList - the ArrayList of Node objects.
      edgeList - the ArrayList of Edge objects.

  • Method Details

    • getName

      public String getName()
      Gets the name of the graph.
      Returns:
      The graph name.

    • addPartialGraph

      public boolean addPartialGraph(List<Node> nodes, List<Edge> edges)
      Adds a partial graph to this graph. Specifically adds a set of nodes and a set of edges to the graph. It should be noted that nodes or edges in the graph already that attempt to be added again may cause exceptions to occur. Additionally, Nodes are added before Edges so any Edges that depend on Nodes in the add list may be safely added simultaneously. This method is the backbone structure for adding any component to the graph as all other addition methods filter through here.
      Parameters:
      nodes - the List<Node> containing the nodes to add.
      edges - the List<Edge> containing the edges to add.
      Returns:
      true, always. Allows overriding in subclasses which wish to change base implementation.

    • getSubGraph

      @Deprecated public Graph getSubGraph(int startNode, int stopNode, String nameQualifier)
      Deprecated.
      Outdated since v3. Replaced by getSubGraph(java.util.List, java.lang.String)
      Returns a subGraph of this graph. Isolates and extracts a subgraph based on user supplied values. The new Graph is a separate Graph object.
      Parameters:
      startNode - the integer pointing to the start node.
      stopNode - the integer pointing to the stop node.
      nameQualifier - the String representing an additional qualifier to prepend the name of the new Graph object with.
      Returns:
      the Graph object representing a subgraph of the original.

    • getSubGraph

      @Deprecated public Graph getSubGraph(ArrayList<String> subStringSet, String nameQualifier)
      Deprecated.
      Outdated since v3. Replaced by getSubGraph(java.util.List, java.lang.String)
      Returns a subGraph of this graph. Isolates and extracts a subgraph based on user supplied values. The new Graph is a separate Graph object.
      Parameters:
      subStringSet - an ArrayList containing the String names of the desired nodes.
      nameQualifier - the String representing an additional qualifier to prepend the name of the new Graph object with.
      Returns:
      the Graph object representing a subgraph of the original.

    • getSubGraph

      public Graph getSubGraph(List<Node> nodes, String nameQualifier)
      Returns a subGraph of this graph. Isolates and extracts a subgraph based on a user supplied node list. The new Graph is a quasi-separate Graph. Each node utilized is directly related between the two graphs and, as such, changes to the properties of one node in the subgraph will be reflected in the super graph. To obtain an independent graph
      Parameters:
      nodes - the List<Node> containing the Node references.
      nameQualifier - the String to differentiate the Graph names.
      Returns:
      the Graph representing the subgraph.

    • transpose

      public void transpose(int node1Index, int node2Index)
      Transposes the specified nodes. Swaps the location of the nodes in memory. Specifically swaps the nodes in the nodeList as the Edge data has been uncoupled from the Node data. Newer implementation is dependent upon the int based method for performance.
      Parameters:
      node1Index - the integer index of the first node.
      node2Index - the integer index of the second node.

    • transpose

      @Deprecated public void transpose(String node1, String node2)
      Deprecated.
      Outdated since v3. Replaced by {}
      Transposes the specified nodes. Swaps the location of the nodes in memory. This is a convenience method for transposing the nodes based on the Sting representation of the nodes.
      Parameters:
      node1 - the String name of the first node.
      node2 - the String name of the second node.

    • transpose

      public void transpose(Node node1, Node node2)
      Transposes the specified nodes. Relies on the integer based method for carrying out the operation.
      Parameters:
      node1 - the Node object in the first position.
      node2 - the Node object in the second position.

    • getGraphWeight

      public double getGraphWeight()
      Get the Graph's total weight (sum of all edge weights)
      Returns:
      the Graph's total weight

    • copy

      public Graph copy()
      Copies this Graph object using the getSubGraph() method.
      Returns:
      a Graph object identical to the original.

    • uniqueCopy

      public Graph uniqueCopy()
      Copies this Graph producing a unique copy in which there is no entanglement between the two Graph objects. I.e. there are no shared nodes or edges between the two graphs. Mathematically speaking: x.getNodeList().get(0) != y.getNodeList().get(0) under any circumstances. The Nodes and Edges may remain equivalent via the equals() implementation. Further, Edge data shall remain entangled due to implementation details.
      Returns:
      a unique copy of the graph object.

    • uniqueCopy

      public Graph uniqueCopy(String gName)

    • union

      public Graph union(Graph that)
      Union this Graph with a provided Graph.
      Parameters:
      that - the Graph to union with
      Returns:
      the Graph that is the union of the two Graphs

    • intersect

      public Graph intersect(Graph that)
      Intersects this Graph with a provided Graph.
      Parameters:
      that - the Graph to intersect with
      Returns:
      the Graph that is the intersection of the two Graphs

    • difference

      public Graph difference(Graph that)
      Difference of this Graph with a provided Graph.
      Parameters:
      that - the Graph to difference with
      Returns:
      the Graph that is the difference of the two Graphs

    • crosstalk

      public Graph crosstalk(Graph subgraph1, Graph subgraph2)
      Crosstalk of 2 subgraphs of this Graph. It is the edges of the 2 subgraphs and the edges that connect the subgraphs. The subgraphs must be disjoint.
      Parameters:
      subgraph1 - subgraph 1
      subgraph2 - subgraph 2
      Returns:
      the crosstalk or empty graph if the subgraphs are not disjoint

    • toString

      public String toString()
      Returns a String representation of the Graph.
      Overrides:
      toString in class Object
      Returns:
      the String representation of the Graph.

    • toStringNameless

      public String toStringNameless()

    • getNodeCount

      public int getNodeCount()
      Gets the number of nodes in the graph.
      Returns:
      the integer representing the total number of nodes in the graph.

    • getNodeList

      public List<Node> getNodeList()
      Returns the list of nodes in the graph.
      Returns:
      the List<Node> containing the list of nodes in the graph.

    • containsNode

      public boolean containsNode(Node node)
      Checks if the graph contains the given node.
      Parameters:
      node - the node to check for
      Returns:
      whether or not node is in this graph

    • addNewNode

      @Deprecated public boolean addNewNode(String node)
      Deprecated.
      Outdated since v3. Replaced by {}
      Adds a node to the graph. Adds the specified node name to the nodeList by creating and adding a new node and then calling the addNode(Node) method.
      Parameters:
      node - the String which denotes the name of the node to add.
      Returns:
      true if the addition was successful.

    • addNode

      public boolean addNode(Node node)
      Adds a node to the graph. Adds a Node object to the graph.
      Parameters:
      node - the Node object to add.
      Returns:
      true if the addition was successful.

    • removeNode

      public void removeNode(Node node)
      Removes a node from the set. Only used with the Bron-Kerbosch algorithm right now, hopefully doesn't break anything Does NOT affect edges!!!!!!! At time of writing may cause issues if you rely on it to do so
      Parameters:
      node - the node to remove

    • addNodes

      public boolean addNodes(List<Node> nodes)
      Adds a list of nodes to the graph.
      Parameters:
      nodes - the List<Node> containing the nodes to add.
      Returns:
      true if the addition was successful.

    • getNodeIndex

      @Deprecated public int getNodeIndex(String node)
      Deprecated.
      Outdated since v3. Replaced by {}
      Gets the index of a node based on its name. Maintained with the new implementation to preserve existing uses. Will not match nodes which may have additional properties attached in future implementations.
      Parameters:
      node - the String representing the node to search for.
      Returns:
      the index of the node or -1 if the node was not found.

    • getNodeIndex

      public int getNodeIndex(Node node)
      Gets the index of a Node object in memory. Retained for older API compatibility. The ordering of the nodes is not guaranteed and may change during the program's runtime.
      Parameters:
      node - the Node object to search for.
      Returns:
      the index of the node or -1 if the node was not found.

    • getNodeName

      @Deprecated public String getNodeName(int nodeIndex)
      Deprecated.
      Outdated since v3. No replacement. Obtain the Node data via the Node object.
      Gets the name of the node at the specified nodeIndex. Ensures that the provided integer is within the range of available indices.
      Parameters:
      nodeIndex - the integer representing the index to get from the headerList.
      Returns:
      the String representing the name of the node.

    • getNode

      public Node getNode(String NodeName)
      Gets a node based on its name.
      Parameters:
      NodeName - the String representing the node to search for.
      Returns:
      the node or null if the node was not found.

    • getAdjacencyList

      public List<Node> getAdjacencyList(Node node)
      Obtains an adjacency list for the supplied node based on the Graph. Very inefficient, try to use the neighbors variable in the Node class instead.
      Parameters:
      node - the Node to obtain the adjacency list for.
      Returns:
      the List of Nodes containing the adjacent Nodes.

    • checkNode

      private void checkNode(Node node)
      Verifies that the node is NOT in the graph. Checks to see if the provided node name is in the headerList and, hence, the dataMatrix. This is an internal method used to ensure that the algorithm is operating correctly.
      Parameters:
      node - the Node to check for.

    • checkNodeIndex

      @Deprecated private void checkNodeIndex(int nodeIndex)
      Deprecated.
      No replacement. Further operations shall utilize {)}
      Verifies that the nodeIndex is valid. Ensures that the node does not fall out of bounds. This is an internal method used to ensure that the algorithm is operating correctly.
      Parameters:
      nodeIndex - the integer of the node to check for.

    • getEdgeCount

      public int getEdgeCount()
      Get the number of Edges in the Graph
      Returns:
      the number of Edges in the Graph

    • getEdgeList

      public List<Edge> getEdgeList()
      Returns the list of edges in the graph.
      Returns:
      the List<Edge> containing the list of edges in the graph.

    • addEdge

      @Deprecated public boolean addEdge(int node1Index, int node2Index, Double edgeData)
      Deprecated.
      Outdated since v3. Replaced by {}
      Adds an edge connecting the specified nodes in the Graph. Sets the object data for the edge dependent upon the supplied parameter.
      Parameters:
      node1Index - the integer value indicating the first node.
      node2Index - the integer value indicating the second node.
      edgeData - the Object that represents unique edge data (i.e. weight or edge relationship).
      Returns:
      true if the addition was successful.

    • addEdge

      @Deprecated public boolean addEdge(String node1, String node2, Double edgeData)
      Deprecated.
      Outdated since v3. Replaced by {
      Adds an edge connecting the specified nodes to the Graph. This is a convenience method for adding an edge using node names. Graphs are undirected so the order of the parameters does not matter.
      Parameters:
      node1 - the String indicating the first node.
      node2 - the String indicating the second node.
      edgeData - the Object that represents unique edge data (i.e. weight or edge relationship).
      Returns:
      true if the addition was successful.

    • addEdge

      public boolean addEdge(Edge edge)
      Adds an edge to the Graph. If any edge already exists within the Graph connecting the two supplied nodes or either of the two nodes is not in the nodeList, then the edge is not added.
      Parameters:
      edge - the Edge object to add to the graph.
      Returns:
      true if the addition was successful.

    • addEdges

      public boolean addEdges(List<Edge> edges)
      Adds a list of Edges to the graph.
      Parameters:
      edges - the List<Edge> containing the edges to add.
      Returns:
      true if the addition was successful.

    • getEdge

      @Deprecated public Object getEdge(int node1Index, int node2Index)
      Deprecated.
      Outdated since v3. No replacement. Obtain the edge first, then obtain the data from the Edge object.
      Gets the value of the edge between the specified nodes.
      Parameters:
      node1Index - the integer value of the first node.
      node2Index - the integer value of the second node.
      Returns:
      the Object representing the edge relationship.

    • getEdge

      @Deprecated public Object getEdge(String node1, String node2)
      Deprecated.
      Outdated since v3. No replacement. Obtain the edge first, then obtain the data from the Edge object.
      Gets the value of the edge between the specified nodes. This is a convenience method for getting the edge using the node's String name.
      Parameters:
      node1 - the String of the first node.
      node2 - the String of the second node.
      Returns:
      the Object representing the edge relationship.

    • getEdge

      public Edge getEdge(Node source, Node destination)
      Locates an Edge object in the edgeList and returns it. Note that it will also return an edge with the provided source and destination parameters swapped IF AN ONLY IF said edge is undirected.
      Parameters:
      source - the source Node of the edge.
      destination - the destination Node of the edge.
      Returns:
      the Edge object or null if not found.

    • getNodeEdges

      public List<Edge> getNodeEdges(Node n)
      Get the list of Edges in which the given Node participates.
      Parameters:
      n - the Node to find edges
      Returns:
      the edges the node participates in

    • removeEdge

      public void removeEdge(Edge e)

    • removeEdgesInvolving

      private void removeEdgesInvolving(Node n)
      Remove all the edges in which the given Node participates.
      Parameters:
      n - the participating Node

    • getEdgesBack

      public List<Edge> getEdgesBack(List<Node> nodes)
      Gets the list edges of this Graph that involve the nodes in the given list
      Parameters:
      nodes - the list of nodes to found the edges from
      Returns:
      the list edges of this Graph that involve the nodes in the given list

    • isClique

      public boolean isClique()
      Determines whether the Graph is a Clique.
      Returns:
      true if the Graph is a Clique

    • isBipartite

      public boolean isBipartite()
      Determines whether the Graph is Bipartite.
      Returns:
      true if the Graph is Bipartite

    • getPartiteSets

      public ArrayList<ArrayList<Node>> getPartiteSets()
      Divides the given graph into two bipartite sets.
      Returns:
      two lists of nodes, each representing a bipartite set. Both lists are empty if the graph is not a valid bipartite graph.

    • isBipartite

      private boolean isBipartite(Node current, Set<Node> addSet, Set<Node> compareSet)
      Private method for stepping through the adjacency lists and determining if the graph is bipartite. Specifically, it uses a Depth-First model for exploring the node tree and sorting the nodes into two groups. If it successfully sorts the nodes into two groups with no invalidating edges, it returns true.
      Parameters:
      addSet - the current set to add a node to based on the previous.
      compareSet - the current set to add adjacent nodes to.
      current - the current Node being compared.
      Returns:
      true if the structure could be bipartite.